<?php
// +----------------------------------------------------------------------
// | 数据结构（Data Structure）
// | 1.线性结构
// | 2.数组、矩阵、广义表
// | 3.数
// | 4.图
// | 5.查找
// | 6.排序
// +----------------------------------------------------------------------
// | 排序方法   最好时间复杂度  平均时间复杂度  最坏时间复杂度  辅助空间  稳定性
// | 直接插入   O(n)          O(n^2)        O(n^2)      O(1)      稳定
// | 冒泡排序   O(n)          O(n^2)        O(n^2)      O(1)      稳定
// | 简单选择   O(n^2)        O(n^2)        O(n^2)      O(1)      不稳定
// | 希尔排序   ——            O(n^1.3)      ——          O(1)      不稳定
// | 快速排序   O(nlogn)      O(nlogn)      O(n^2)      O(nlogn)  不稳定
// | 堆排序     O(nlogn)      O(nlogn)     O(nlogn)     O(1)      不稳定
// | 归并排序   O(nlogn)      O(nlogn)     O(nlogn)     O(n)      稳定
// | 基数排序   O(d(n+rd))    O(d(n+rd))   O(d(n+rd))   O(rd)     稳定
// +----------------------------------------------------------------------

namespace helper\structure;

class Sort
{
    /**
     * 直接插入排序
     * -------------------------------------------------------------
     * 思路分析：每步将一个待排序的纪录，按其关键码值的大小插入前面已经排序的文件中适当位置上，直到全部插入完为止。
     * -------------------------------------------------------------
     *
     * 插入算法把要排序的数组分成两部分：第一部分包含了这个数组的所有元素，
     * 但将最后一个元素除外（让数组多一个空间才有插入的位置），而第二部分就只包含这一个元素（即待插入元素）。
     * 在第一部分排序完成后，再将这个最后元素插入到已排好序的第一部分中。
     * @param array $data
     * @return array
     */
    function insertSort(array $data): array
    {
        // 1、认定第一个元素已经排好序；
        $count = count($data);
        for ($i = 1; $i < $count; $i++) {
            // 2、取出第二个元素，作为待插入数据；
            $temp = $data[$i];//$temp是准备插入的数
            // 3、与已经排好序的数组的最右侧元素开始进行比较
            $j    = $i - 1;//有序表中准备比较的数的下标
            // 4、如果后面的小于前面的：说明前面已经排好序的那个数组元素不在对的位置（向后移一个），然后让新的元素填充进去（继续向前比：高级）
            while ($j >= 0 && $data[$j] > $temp) {
                $data[$j + 1] = $data[$j];//将数组往后挪
                $j--; //将下标往前挪，准备与前一个进行比较
                // 5、重复前面的步骤：直到当前元素插入到对位置；
            }
            if ($i != $j + 1) {
                $data[$j + 1] = $temp;
            }
            // 6、重复以上步骤，直到所有的数组元素都插入到对的位置。
        }
        return $data;
    }

    /**
     * 冒泡排序（Bubble Sort）
     * 基本原理：重复的走访(遍历)要排序的数列，比较相邻的两个数，把大的数移到右边，接着遍历，直到所有数完成从小到大的顺序。
     * 走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。
     * -------------------------------------------------------------
     * 思路分析：就是像冒泡一样，每次从数组当中 冒一个最大的数出来。
     * -------------------------------------------------------------
     * 你可以这样理解：（从小到大排序）存在10个不同大小的气泡，由底至上的把较少的气泡逐步地向上升，
     * 这样经过遍历一次后最小的气泡就会被上升到顶（下标为0），然后再从底至上地这样升，循环直至十个气泡大小有序。
     *
     * @param array $data
     * @return array
     */
    function bubbleSort(array $data): array
    {
        $count = count($data);
        // 2.想办法让下面可以每次找出最大值的代码重复执行
        for ($j = 1; $j < $count; $j++) {
            // 1.想办法将最大的值放到最右边去
            for ($i = 0; $i < $count - $j; $i++) {
                // 判断:两两比较
                if ($data[$i] > $data[$i + 1]) {
                    //左边比右边大:交换
                    $temp         = $data[$i];
                    $data[$i]     = $data[$i + 1];
                    $data[$i + 1] = $temp;
                }
            }
        }
        return $data;
    }

    /**
     * 简单选择排序
     * -------------------------------------------------------------
     * 基本方法：对于n个记录，通过n-i（1<=i<=n）在次关键字之间的比较，从n-i+1个记录中选出关键字最小的记录，并和第i个记录进行交换，
     * 当i=n时所有记录有序排列
     * @param array $data
     * @param int $n
     * @return array
     */
    function selectSort(array $data, int $n = 0): array
    {
        //1.确定要交换多少次,一次只能找到一个最小的,需要找数组长度
        $n = $n ?: count($data);
        for ($i = 0; $i < $n - 1; $i++) {
            $k = $i;
            // 找到最小关键字的下标
            for ($j = $i + 1; $j < $n; $j++) {
                if ($data[$j] < $data[$k]) {
                    $k = $j;
                }
            }
            if ($k != $i) {
                $temp          = $data[$i];
                $data[$i] = $data[$k];
                $data[$k] = $temp;
            }
        }
        return $data;
    }

    /**
     * 希尔排序[缩小增量排序]
     * -------------------------------------------------------------
     * 希尔排序是对插入排序的改进，区别在于插入排序是相邻的一个个比较（类似于希尔中h=1的情形），而希尔排序是距离h的比较和替换。
     * 基本思想：先将整个待排记录序列分割成若干子序列，然后分别进行直接插入排序，待整个序列中的记录基本有序时，再对全体记录进行一次直接插入排序
     * @param array $container
     * @return array
     */
    function shellSort(array $container): array
    {
        $count = count($container);
        for ($increment = intval($count / 2); $increment > 0; $increment = intval($increment / 2)) {
            for ($i = $increment; $i < $count; $i++) {
                $temp = $container[$i];
                for ($j = $i; $j >= $increment; $j -= $increment) {
                    if ($temp < $container[$j - $increment]) {
                        $container[$j] = $container[$j - $increment];
                    } else {
                        break;
                    }
                }
                $container[$j] = $temp;
            }
        }
        return $container;
    }

    /**
     * 快速排序 [教科书版]
     * -------------------------------------------------------------
     * 基本思想：通过一趟排序将待排序的记录划分为独立的两个部分，其中一部分记录的关键字均不大于另一部分的关键字，
     * 然后再分别对这两部分记录进行快速排序，以达到整个序列有序。
     * @param array $data data[low...high]
     * @param int $low
     * @param int $high
     */
    function quickSort(array &$data, int $low = 0, int $high = 0)
    {
        $high = $high ?: count($data) - 1;
        if ($low < $high) {
            // 以数组的第一个元素为基准（枢轴元素）进行划分
            $pivotKey = $data[$low];
            $i        = $low;
            $j        = $high;
            while ($i < $j) {
                // 从数组的两端交替的向中间扫描
                while ($i < $j && $data[$j] >= $pivotKey) {
                    $j--;
                }
                if ($i < $j) {
                    $data[$i++] = $data[$j];// 比枢轴元素小者移到低下标端
                }
                while ($i < $j && $data[$i] < $pivotKey) {
                    $i++;
                }
                if ($i < $j) {
                    $data[$j--] = $data[$i];// 比枢轴元素大者移到高下标端
                }
            }
            $data[$i] = $pivotKey;// 枢轴元素移到正确位置
            $this->quickSort($data, $low, $i - 1);
            $this->quickSort($data, $i + 1, $high);
        }
    }

    /**
     * 快速排序 [效率较低版]
     * 1）  从数组中选出一个元素（通常第一个），作为参照对象。
     * 2）  定义两个数组，将目标数组中剩余的元素与参照元素挨个比较：小的放到一个数组，大的放到另外一个数组。
     * 3）  第二步执行完之后，前后的数组顺序不确定，但是确定了自己的位置。
     * 4）  将得到的小数组按照第1到第3部重复操作（子问题）。
     * 5）  回溯最小数组（一个元素）。
     */
    function quickSorts($array)
    {
        if (count($array) <= 1) return $array;
        // 1）通过设置一个初始中间值，来将需要排序的数组分成3部分，小于中间值的左边，中间值，大于中间值的右边
        $key        = $array[0];
        $rightArray = array();
        $leftArray  = array();

        for ($i = 1; $i < count($array); $i++) {
            if ($array[$i] >= $key) {
                $rightArray[] = $array[$i];
            } else {
                $leftArray[] = $array[$i];
            }
        }
        // 2）继续递归用相同的方式来排序左边和右边
        $leftArray  = $this->quickSorts($leftArray);
        $rightArray = $this->quickSorts($rightArray);
        // 3）合并排序后的数据，别忘了合并中间值
        return array_merge($leftArray, array($key), $rightArray);
    }

    /**
     * 将整型数组元素调成大根堆
     * @param array $data
     * @param int $s
     * @param int $m
     * @return void
     */
    private function heapAdjust(array &$data, int $s, int $m)
    {
        $t = $data[$s];
        for ($j = 2 * $s + 1; $j <= $m; $j = $j * 2 + 1) {
            if ($j < $m && $data[$j] < $data[$j + 1]) {
                ++$j;
            }
            if ($t < $data[$j]) {
                break;
            }
            $data[$s] = $data[$j];
            $s        = $j;
        }
        $data[$s] = $t;
    }

    /**
     * 堆排序 (大根堆)
     * -------------------------------------------------------------
     * 基本思想：对一组待排序的关键字，首先按堆的定义排成一个序列（即建立初始堆），从而可以输出堆顶的最大关键字（对于大根堆而言），
     * 然后将剩余的关键字再调整成新堆，边得到次大的关键字，如此反复，知道全部关键字排成有序序列为止
     */
    function heapSort(array $data): array
    {
        $n = count($data) - 1;
        for ($i = $n / 2 - 1; $i > 0; --$i) {
            // 把data[0..n-1]调整为大根堆
            $this->heapAdjust($data, $i, $n - 1);
        }
        for ($i = $n - 1; $i > 0; --$i) {
            // 堆顶元素$data[0]与系列的最后元素$data[$i]交换
            $t        = $data[0];
            $data[0]  = $data[$i];
            $data[$i] = $t;
            // 待排序元素的个数减1，将data[0..$i-1]重新调整为大根堆
            $this->heapAdjust($data, 0, $i - 1);
        }
        return $data;
    }

    /**
     * 两路归并
     * 将一维数组中前后两个有序序列归并成一个有序序列
     * @param array $data data[s..m],data[m+1,n]归并为有序的data[s..n]
     * @param int $s
     * @param int $m
     * @param int $n
     * @return void
     */
    private function merge(array &$data, int $s, int $m, int $n)
    {
        $temp = $data;//辅助空间
        $k    = $s;// 左堆起始
        $i    = $m + 1;// 右堆起始
        // 左右堆数组都没到末尾
        while ($s <= $m && $i <= $n) {
            // 左堆小于右堆时
            if ($temp[$s] < $temp[$i]) {
                $data[$k++] = $temp[$s++];// 左堆赋给临时数组,索引加1
            } else {
                $data[$k++] = $temp[$i++];// 右堆赋给临时数组,索引加1
            }
        }
        // 左堆剩余的全部加进临时数组
        while ($s <= $m) {
            $data[$k++] = $temp[$s++];
        }
        // 右堆剩余全部加进临时数组
        while ($i <= $n) {
            $data[$k++] = $temp[$i++];
        }
        unset($temp);
    }

    /**
     * 归并排序
     * @param array $data data[s..t]
     * @param int $s
     * @param int $t
     */
    public function mergeSort(array &$data, int $s, int $t)
    {
        // 最左只能小于最右,等于的时候就一个元素,大于是不可能的
        if ($s >= $t) {
            return;
        }
        // 分治法步骤：
        // 1）分解
        $m = intval(($s + $t) / 2);// 获取中间的元素
        // 2）求解
        $this->mergeSort($data, $s, $m);// 递归左半区
        $this->mergeSort($data, $m + 1, $t);// 递归右半区
        // 3）合并
        $this->merge($data, $s, $m, $t);
    }

    /**
     * 归并排序
     * @param array $arr
     * @return array
     */
    function mergeSorts(array $arr): array
    {
        $length = count($arr);
        if ($length <= 1) {
            return $arr;
        }
        // 1）将数组拆分成两个数组。
        //分解数组，递归排序
        $half = ceil($length / 2);
        $arr2 = array_chunk($arr, $half);
        // 2）重复步骤1将数组拆分成最小单元。
        $left  = $this->mergeSorts($arr2[0]);
        $right = $this->mergeSorts($arr2[1]);
        // 3）申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列.
        // 4）设定两个指针，最初位置分别为两个已经排序序列的起始位置。
        $reg = [];
        while (count($left) && count($right)) {
            // 5）  比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置。
            if ($left[0] < $right[0]) {
                $reg[] = array_shift($left);
                // 6）  重复步骤3直到某一指针超出序列尾。
            } else {
                // 7）  将另一序列剩下的所有元素直接复制到合并序列尾。
                $reg[] = array_shift($right);
            }
        }
        return array_merge($reg, $left, $right);
    }

    /**
     * 基数排序
     * @param array $arr
     * @return array
     */
    function radixSort(array $arr): array
    {
        $arr_len = count($arr);
        if ($arr_len <= 1) {
            return $arr;
        }
        // 1、取出数组中最大值，算出来有多少位
        $max = max($arr); // 用Math的max函数获取数组中的最大值
        $max_len = strlen($max); // 获取最大的数的位数
        $radix = 1; // 基数,从最后一位数开始
        // 2、从个位开始取余数，根据余数将数据放入0-9的桶中
        for ($i = 0; $i < $max_len; $i ++) { // 按最大位数读取各位的数
            for ($j = 0; $j < 10; $j ++) {
                $buckets[$j] = []; // 用来装不同基数对应的值
            }
            foreach ($arr as $val) { // 按基数把数放到桶里
                $buckets[($val / $radix) % 10][] = $val;
            }

            $radix *= 10; // 基数进位
            // 3、将桶中的数据取出来填充到原来的数组中
            $k = 0;
            $arr = [];
            foreach ($buckets as $bucket) { // 把桶里的数重新存起来
                foreach ($bucket as $val) {
                    $arr[$k++] = $val;
                }
            }
            // 4、重复2、3步骤对十位、百位...取余、装桶、回填，完成排序
        }
        return $arr;
    }

    /**
     * 计数排序
     * 复杂度为Ο(n+k)
     * @param $arr
     * @return mixed
     */
    public function countingSort($arr)
    {
        // 1、找出最大值，最小值
        $maxValue = max($arr);
        // 2、根据数组的长度，创建出若干个桶
        $bucket = [];
        for ($m = 0; $m < $maxValue + 1; $m ++) {
            $bucket[] = null;
        }

        $arrLen = count($arr);
        // 3、遍历数组的元素，根据元素的值放入到对应的桶中
        for ($i = 0; $i < $arrLen; $i ++) {
            // 4、对每个桶的元素进行排序(可使用快排，插入排序等)。
            if (!array_key_exists($arr[$i], $bucket)) {
                $bucket[$arr[$i]] = 0;
            }
            $bucket[$arr[$i]] ++;
        }

        $sortedIndex = 0;
        // 5、按顺序合并每个桶的元素，排序完成 按照桶的顺序取数据，生成一个新的有序数组
        foreach ($bucket as $key => $len) {
            if ($len !== null) {
                for ($j = 0; $j < $len; $j ++) {
                    $arr[$sortedIndex ++] = $key;
                }
            }
        }
        return $arr;
    }

    /**
     * 飞梭排序
     * -------------------------------------------------------------
     * 思路分析：飞梭排序是冒泡排序的轻微变形。不同的地方在于，飞梭排序是从低到高然后从高到低来回排序，而冒泡排序则仅从低到高去比较序列里的每个元素。
     * -------------------------------------------------------------
     * 先对数组从左到右进行冒泡排序（升序），则最大的元素去到最右端
     * 再对数组从右到左进行冒泡排序（降序），则最小的元素去到最左端
     * 以此类推，依次改变冒泡的方向，并不断缩小未排序元素的范围，直到最后一个元素结束
     * -------------------------------------------------------------
     *
     * @param array $data
     * @return array
     */
    function shuttleSort(array $data): array
    {
        /**
         * 替换方法
         *
         * @param array $data
         * @param       $i
         * @param       $j
         * @return array
         */
        $swap = function (array &$data, $i, $j) {
            $temp     = $data[$i];
            $data[$i] = $data[$j];
            $data[$j] = $temp;
            return $data;
        };

        $count = count($data);
        $left  = 0;
        $right = $count - 1;

        while ($left < $right) {
            // 从左到右
            $lastRight = 0;
            for ($i = $left; $i < $right; $i++) {
                if ($data[$i] > $data[$i + 1]) {
                    $swap($data, $i, 1 + $i);
                    $lastRight = $i;
                }
            }
            $right = $lastRight;
            // 从右到左
            $lastLeft = 0;
            for ($j = $right; $left < $j; $j--) {
                if ($data[$j - 1] > $data[$j]) {
                    $swap($data, $j - 1, $j);
                    $lastLeft = $j;
                }
            }
            $left = $lastLeft;
        }
        return $data;
    }
}